package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.Node;

/**
 * @author jiazhaoxin
 * @Date 2022/2/12
 * @Desc {https://leetcode-cn.com/problems/copy-list-with-random-pointer/}
 */
public class 复制随机指针链表 {

    public Node copyRandomList(Node head) {
        if(head==null){
            return head;
        }
        copyNext(head);
        copyNRandom(head);
        return split(head);
    }

    public void copyNext(Node head){
        Node dummy = head;
        while(dummy!=null){
            Node nextNode = dummy.next;
            dummy.next = new Node(dummy.val);
            dummy.next.next = nextNode;
            dummy = nextNode;
        }
    }

    public void copyNRandom(Node head){
        Node dummy = head;
        while(dummy!=null&& dummy.next!=null){
            if(dummy.random!=null){
                dummy.next.random = dummy.random.next;
            }
            dummy  = dummy.next.next;;
        }
    }

    public Node split(Node head){
        Node newNode=head.next ;
        Node knife = head.next;
        while(head!=null&&head.next!=null){
            head.next = head.next.next;
            head = head.next;
            //切割copy-Random节点和 next节点的关系
            if(knife!=null&& knife.next!=null){
                knife.next = knife.next.next;
                knife = knife.next;
            }
        }
        return newNode;
    }
}
